package org.example.sword2offer.primary;

/**
 * @author: lynn
 * @Descript: 反转单链表,注意单链表的定义
 * Question 3
 * @date: 2021/3/7 20:09
 * @version: 1.0
 */
public class Q3_ReverseNodeList {
    public static void main(String[] args) {
        ListNode<Integer> listNode=new ListNode<Integer>(5);
        listNode.next=new ListNode(6);
        listNode.next.next=new ListNode(9);
        listNode.next.next.next=new ListNode(11);
        listNode=reverseNode(listNode);
        System.out.println(listNode);
    }
    /**
     * 节点ListNode, 数据域，以及指针
     * @param <T>
     */
    private static class ListNode<T>{
        private T data;//数据域
        private ListNode next;//指针域
        public ListNode(T data){
            this.data = data;
        }
        public ListNode(T data,ListNode next){
            this.data = data;
            this.next = next;
        }
        public T getData() {
            return data;
        }
        public void setData(T data) {
            this.data = data;
        }
        public ListNode getNext() {
            return next;
        }
        public void setNext(ListNode next) {
            this.next = next;
        }
        @Override
        public String toString() {
            return data.toString();
        }
    }

/*
所谓的单链表反转，就是把每个节点的指针域由原来的指向下一个节点变为指向其前一个节点。
但由于单链表没有指向前一个节点的指针域，因此我们需要增加一个指向前一个节点的指针pre，
用于存储每一个节点的前一个节点。此外，还需要定义一个保存当前节点的指针cur，以及下一个节点的next。
定义好这三个指针后，遍历单链表，将当前节点的指针域指向前一个节点，之后将定义三个指针往后移动，直至遍历到最后一个节点停止。
*/

/*
这个的思路就是 俩个指针，把一个链表分成俩个部分， preNode是已经反转部分，
curNode是为反转部分，然后通过俩个指针的配合，不断的右移直到前部反转
 */

    private static ListNode reverseNode(ListNode  head){
        if(head == null || head.next == null){
            return head;
        }
        ListNode preNode = null;//前一个节点指针
        ListNode curNode = head;//当前节点指针
        while (curNode != null){
            ListNode nextNode = curNode.getNext();//nextNode 指向下一个节点
            curNode.setNext(preNode);//将当前节点next域指向前一个节点
            preNode = curNode;//preNode 指针向后移动
            curNode = nextNode;//curNode指针向后移动
        }
        return preNode;
    }
}
